class Solution(object):
    def decodeAtIndex(self, s, k):
        if k == 1:
            return s[0]
        prefix = []
        n = len(s)
        prefix.append(1)
        for i in range(1, n):
            if 'a' <= s[i] <= 'z':
                prefix.append(prefix[-1] + 1)
            else:
                prefix.append(int(s[i]) * prefix[-1])
            if prefix[-1] >= k:
                break
        m = len(prefix)
        for j in range(m - 1, -1, -1):
            if prefix[j] == k:
                if 'a' <= s[j] <= 'z':
                    return s[j]
                else:
                    k = prefix[j - 1]
            else:
                k = k % prefix[j - 1]
                if k == 0:
                    k = prefix[j - 1]
        return s[0]


data = Solution()
s = "vk6u5xhq9v"
k = 554
print(data.decodeAtIndex(s, k))

